package com.mgq.algorithm.greedy;

import java.util.PriorityQueue;

/**
 * @author MaGuangQi
 * 切金条问题(哈夫曼树问题)
 * 给一个金条,给一个数组,数组内是每个人需要的长度.金条切分成需要的长度,长度是多少
 * 就要花费多少铜板,比如{10,20,30}. 金条长度是60. 要求怎么才能花费最小的铜板
 * 切法一: 如果一开始切10和50,然后50再切20,30 需要花费 10+50+20+30=110 铜板
 *
 *切法二:一开始切30和30,把30切成10和20 需要花费的钱是30+30+10+20=90 铜板
 * 90就是这个的最优解
 * @date 2022-01-05 16:56
 **/
public class LessMoneySplitGold {
    /**
     * 把所有的值加入到小根堆,每次弹出2个.相加,将结果再加入到小根堆,
     * 以此类推,最后得到的结果就是最小花费的值
     * {10,20,30}举例
     * sum=0
     * 10,20 sum=30
     * 30,30 sum=30+60=90
     * @param arr
     * @return
     */
    public static int lessMoney(int[] arr) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.add(arr[i]);
        }
        int sum=0;
        //不能少于2个
        while (priorityQueue.size() > 1) {
            int cur = priorityQueue.poll() + priorityQueue.poll();
            sum += cur;
            priorityQueue.add(cur);
        }
        return sum;
    }

    public static void main(String[] args) {
        int i = lessMoney(new int[]{10, 20, 40,30});
        System.out.println(i);
    }
}
